The problems of authentication—proving that a product, computer, device, or person is who they say they are—were addressed theoretically in 1976 by Whitfield Diffie and Martin Hellman when they published their concepts for a method of exchanging secret messages without exchanging secret keys. The idea came to fruition in 1977 with the invention of the RSA Public Key Cryptosystem. The RSA Public Key Cryptosystem can be used for encrypting and authenticating, i.e. digitally signing, documents. The RSA system uses large prime numbers in the generation of the public/private keypair. While this functions quite well in large systems such as computers, for limited capability systems—for example RFID tags, smart cards, or other devices having either limited memory or limited computational capability—the RSA public key cryptography system cannot be used.
Radio-frequency identification (RFID) tags are becoming more common. They are being used for tracking products, and other objects. Some RFID tags may include an Electronic Product Code (EPC). FIG. 1 describes an exemplary EPC system.
When an RFID tag is manufactured with an EPC, the EPC is registered within the Electronic Product Code Information System (EPC-IS). The RFID tag is attached to a product and the EPC becomes a part of that product as it moves through the supply chain. The particular product information is added to the manufacturer's EPC-IS, and the knowledge that this data exists within the manufacturer's EPC-IS is passed to the EPC Discovery Service.
When the product leaves the manufacturer's facility, its departure is automatically registered with the EPC-IS. Likewise, when the product arrives at the next point in the supply chain (e.g., a distributor site) it is automatically read and registered with the distributor's EPC-IS and with the EPC Discovery Service.
When the distributor, retailer, or potentially final consumer needs product information, it uses a query application to query the manufacturer's EPC-IS. The query application uses the Object Name Service (ONS) to find the appropriate EPC-IS server. The query application contacts its local ONS server to find the appropriate EPC-IS server. If the local ONS server does not have the appropriate record in its cache, it will query the root ONS Server to find the location of the manufacturer's ONS Server, which in turn provides the location of the manufacturer's ONS server, and finally the appropriate EPC-IS server. This query process is transparent to the requester takes only milliseconds to execute. With the manufacturer's EPC-IS location, the distributor's application can request specific product information. As products progress through the supply chain, they are in constant communication with the EPC-IS. The result is real-time full visibility of the supply chain.
Many business applications rely on accurate information about products in the supply chain. For example, pharmaceutical manufacturers, distributors, and retailers need to protect consumers against counterfeit goods. Without a cryptographic mechanism, it is impossible to electronically validate that individual items are authentic. Therefore, an improved cryptographic mechanism that would be usable in low complexity systems such as RFID tags or smart cards would be useful.